package leetcode_200;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *@author 周杨
 *DistinctSubsequences_115 给定两个字符串  输出字符串2在字符串1中出现了多少次  (顺序相同即可)
 *describe:用动态规划 AC 42%
 *2018年5月22日 上午10:33:07
 */
public class DistinctSubsequences_115 {

	public static void main(String[] args) {
		DistinctSubsequences_115 test=new DistinctSubsequences_115();
		System.out.println(test.numDistinct("babgbag", "bag"));
		System.out.println(test.numDistinct("rabbbit", "rabbit"));
		System.out.println(test.numDistinct("rabbbit", "r"));

	}
	
	/**
	 * describe:dp[i][j] i表示s中的第几个数字 j表示t中的第几个数字  dp[i][j]表示当指针到s第i个字符时 此时s中0-j这个子串出现了多少次
	 * 2018年5月22日 上午10:35:52
	 */
	public int numDistinct(String s, String t) {
		int dp[][]=new int[s.length()+1][t.length()+1];
		Map<Character,List<Integer>> map=new HashMap<Character,List<Integer>>();
		for(int i=0;i<t.length();++i) {
			char c=t.charAt(i);
			List<Integer> list=map.get(c);
			if(list==null) {
				list=new ArrayList<Integer>();
				list.add(i+1);
				map.put(c, list);
			}
			else {
				list.add(i+1);
			}
		}
		for(int i=0;i<dp.length;++i) {
			dp[i][0]=1;
		}
		for(int i=1;i<s.length()+1;++i) {
			char c=s.charAt(i-1);
			List<Integer> list=map.get(c);
			if(list!=null&&list.size()>0) {
				for(int j=list.size()-1;j>=0;--j) {//逆序取Index
					int index=list.get(j);
					dp[i][index]=dp[i-1][index]+dp[i-1][index-1];
				}
			}
			for(int j=1;j<t.length()+1;++j) {
				if(dp[i][j]<dp[i-1][j])
					dp[i][j]=dp[i-1][j];
			}
		}
        return dp[s.length()][t.length()];
    }

}
